翻訳と辞書 Words near each other ・ Shorty Castro ・ Shorty da Prince ・ Shorty Dee ・ Shorty Fuller ・ Shorty Gallagher ・ Shorty Green ・ Shorty Hamilton ・ Shorter University ・ Shorter Views ・ Shorter, Alabama ・ Shorter, Faster, Louder ・ Shorterville, Alabama ・ Shortest common supersequence problem ・ Shortest job next ・ Shortest Path Faster Algorithm ・ Shortest path problem ・ Shortest remaining time ・ Shortest river ・ Shortest seek first ・ Shortest tennis match records ・ Shortest total path length spanning tree ・ Shortest-path tree ・ Shortfin barb ・ Shortfin false moray ・ Shortfin lizardfish ・ Shortfin mako shark ・ Shortfin sandskate ・ Shortfin saury ・ Shortfin smooth lanternshark ・ Shortfinned worm eel Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Shortest path problem ： ウィキペディア英語版 Shortest path problem In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between two intersections on a road map (the graph's vertices correspond to intersections and the edges correspond to road segments, each weighted by the length of its road segment) may be modeled by a special case of the shortest path problem in graphs. ==Definition== The shortest path problem can be defined for graphs whether undirected, directed, or mixed. It is defined here for undirected graphs; for directed graphs the definition of path requires that consecutive vertices be connected by an appropriate directed edge. Two vertices are adjacent when they are both incident to a common edge. A path in an undirected graph is a sequence of vertices $P\; =\; (\; v\_1,\; v\_2,\; \backslash ldots,\; v\_n\; )\; \backslash in\; V\; \backslash times\; V\; \backslash times\; \backslash ldots\; \backslash times\; V$ such that $v\_i$ is adjacent to $v\_$ for . Such a path $P$ is called a path of length $n$ from $v\_1$ to $v\_n$. (The $v\_i$ are variables; their numbering here relates to their position in the sequence and needs not to relate to any canonical labeling of the vertices.) Let $e\_$ be the edge incident to both $v\_i$ and $v\_j$. Given a real-valued weight function $f:\; E\; \backslash rightarrow\; \backslash mathbb$, and an undirected (simple) graph $G$, the shortest path from $v$ to $v\text{'}$ is the path $P\; =\; (\; v\_1,\; v\_2,\; \backslash ldots,\; v\_n\; )$ (where $v\_1\; =\; v$ and $v\_n\; =\; v\text{'}$) that over all possible $n$ minimizes the sum $\backslash sum\_^\; f(e\_).$ When each edge in the graph has unit weight or $f:\; E\; \backslash rightarrow\; \backslash$, this is equivalent to finding the path with fewest edges. The problem is also sometimes called the single-pair shortest path problem, to distinguish it from the following variations: * The single-source shortest path problem, in which we have to find shortest paths from a source vertex ''v'' to all other vertices in the graph. * The single-destination shortest path problem, in which we have to find shortest paths from all vertices in the directed graph to a single destination vertex ''v''. This can be reduced to the single-source shortest path problem by reversing the arcs in the directed graph. * The all-pairs shortest path problem, in which we have to find shortest paths between every pair of vertices ''v'', ''v' '' in the graph. These generalizations have significantly more efficient algorithms than the simplistic approach of running a single-pair shortest path algorithm on all relevant pairs of vertices. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Shortest path problem」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.